class Solution {
    public:
        bool isInterleave(string s1, string s2, string s3) {
            s1 = " "+s1;
            s2 = " "+s2;
            s3 = " "+s3;
            int m = s1.size(),n = s2.size() , k = s3.size();
            vector<vector<bool>> dp(m,vector<bool>(n));
            if(m + n != k+1) return false;
            dp[0][0] = true;
            for(int i = 1 ; i < n ; i++){
                if( s2[i] == s3[i]){
                    dp[0][i] = true;
                }else{
                    break;
                }
            }
            for(int i = 1 ; i < m ; i++){
                if(s1[i] == s3[i]){
                    dp[i][0] = true;
                }else{
                    break;
                }
            }
            for(int i = 1 ; i < m ; i++){
                for(int j = 1 ; j < n ;j++){
                    dp[i][j] = (s1[i] == s3[i+j]&&dp[i-1][j]) ||
                                (s2[j] == s3[i+j]&& dp[i][j-1]);
                }
            }
    
            return dp[m-1][n-1];
        }
    };